#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<omp.h>

typedef unsigned long long int  ullint;

ullint divisorValido(ullint n, ullint *r, ullint m){
	ullint i;
	for(i=0; i<m; i++){
		if(n%r[i]==0){
			printf("part i: %llu ",i);
			return r[i];
		}
	}
	
	printf("ERRO divisorValido\n");
	
	return 0;
}

ullint geraDivisorPart(ullint n, ullint f, ullint i, ullint m, ullint raiz){
	ullint tamPart = (double) ceill(((double)raiz-(double)f)/(double)m);
	ullint inicio = f+tamPart*i;
	ullint fim = inicio + tamPart;
	ullint j;
	
	//printf("part i: %lld - tamPart: %lld - inicio: %lld - fim: %lld - n:%lld - f:%lld \n", i, tamPart, inicio, fim, n,f);
	
	for(j=inicio; j<=fim; j+=j%2==0?1:2){

				
		if(n%j==0){
//			printf("part i: %lld - j:%lld\n",i,j);			
			return j;			
		}
		
	}
		
	//printf("part i: %lld - fim:%lld\n",i,fim);
	return fim;
}

ullint geradordivisor(ullint n, ullint f){
	
	ullint m=4;
	ullint r[m+1];
	ullint i=0;
	ullint raiz=sqrt(n);
		
#pragma omp parallel for
	for(i=0; i<m; i++){
		r[i] = geraDivisorPart(n,f,i,m,raiz);
	}
	
	r[m]=n;
	
	return divisorValido(n,r,m+1);
}

void fatoracaoPrimos(ullint n, ullint f){
	
	if(n==1){
		return;
	}
	
	ullint divisor = geradordivisor(n,f);
	printf("%llu \n",divisor);
	
	
	fatoracaoPrimos(n/divisor, divisor);
}

int main(int argc, char **argv){
	char *a;
    ullint n = strtoull(argv[1], &a, 10);
	printf ("%llu \n", n);
	
    fatoracaoPrimos(n,2);
	
	printf ("\n");
    return 0;
}
